package algorithm.sort.quick;


import algorithm.sort.base.ArrayUtils;

public class QuickSort2 {
    public static void sort(int[] data) {
        sortPart(data, 0, data.length - 1);
    }

    public static void sortPart(int[] data, int start, int end) {
        if (end > start) {
            int mid = partition(data, start, end);
            sortPart(data, start, mid - 1);
            sortPart(data, mid + 1, end);
        }
    }

    public static int partition(int[] data, int leftIndex, int rightIndex) {
        int pivot = leftIndex;
        int lowerIndex = leftIndex+1;
        for (int i = lowerIndex; i <= rightIndex; i++) {
            if (data[i] <  data[pivot] ) {
                ArrayUtils.swap(data, lowerIndex, i);
                lowerIndex++;
            }
        }
        ArrayUtils.swap(data, pivot, lowerIndex-1);
        return lowerIndex-1;
    }
}
